<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Графы (advanced)</h2>
<ol>
  <li>Алгоритм Йена (поиск k-го кратчайшего пути)</li>
  <li>Раскраски</li>
  <ol>
    <li>Раскраска вершин двудольного графа в k цветов за O(V<sup>2</sup>E)</li>
    <li>Раскраска вершин двудольного графа в k цветов за O(VElogV) и O(EsqrtVlogV)</li>
  </ol></li>
  <li>Лексмин</li>
  <ol>
    <li>На ребрах написаны символы. Найти кратчайший (весов нет) лексикографически минимальный путь из a в b за O(E).</li>
    <li>На ребрах написаны символы. Найти лексикографически минимальный путь из a в b за O(VE).</li>
    <li>На ребрах написаны символы. Найти лексикографически минимальный путь из a в b за O(ElogV).</li>
  </ol></li>
  <li>Транзитивное замыкание графа (матрица достижимости, Флойд) за V<sup>3</sup>/32</li>
  <li>Циклы</li>
  <ol>
    <li>Поиск отрицательного цикла за O(VE)</li>
    <li>Поиск цикла минимального среднего веса за O(VElogM)</li>
    <li>Поиск цикла минимального среднего веса за O(VE)</li>
    <li>Поиск Эйлерова цикла за O(E)</li>
    <li>Дополнение графа до Эйлерова</li>
    <li>Разбить все ребра графа на минимальное количество путей (каждое ребро входит в ровно один путь) за O(E)</li>
    <li>Поиск цикла за O(E) в орграфе</li>
    <li>Поиск цикла за O(E) в неорграфе</li>
    <li>Поиск цикла за O(V) в неорграфе</li>
  </ol></li>
</ol>
